Search Results

Documents authored by Telle, Jan Arne

Document
DOI: 10.4230/LIPIcs.STACS.2022.38
Classes of Intersection Digraphs with Good Algorithmic Properties

Authors: Lars Jaffke, O-joung Kwon, and Jan Arne Telle

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions towards a better understanding of the algorithmic treatment of intersection digraphs. First, we introduce natural classes of intersection digraphs that generalize several classes studied in the literature. Second, we define the directed locally checkable vertex (DLCV) problems, which capture many well-studied problems on digraphs such as (Independent) Dominating Set, Kernel, and H-Homomorphism. Third, we give a new width measure of digraphs, bi-mim-width, and show that the DLCV problems are polynomial-time solvable when we are provided a decomposition of small bi-mim-width. Fourth, we show that several classes of intersection digraphs have bounded bi-mim-width, implying that we can solve all DLCV problems on these classes in polynomial time given an intersection representation of the input digraph. We identify reflexivity as a useful condition to obtain intersection digraph classes of bounded bi-mim-width, and therefore to obtain positive algorithmic results.
Cite as

Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Classes of Intersection Digraphs with Good Algorithmic Properties. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.STACS.2022.38,
  author =	{Jaffke, Lars and Kwon, O-joung and Telle, Jan Arne},
  title =	{{Classes of Intersection Digraphs with Good Algorithmic Properties}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.38},
  URN =		{urn:nbn:de:0030-drops-158480},
  doi =		{10.4230/LIPIcs.STACS.2022.38},
  annote =	{Keywords: intersection digraphs, H-digraphs, reflexive digraphs, directed domination, directed H-homomorphism}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.47
Hierarchical Clusterings of Unweighted Graphs

Authors: Svein Høgemo, Christophe Paul, and Jan Arne Telle

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We study the complexity of finding an optimal hierarchical clustering of an unweighted similarity graph under the recently introduced Dasgupta objective function. We introduce a proof technique, called the normalization procedure, that takes any such clustering of a graph G and iteratively improves it until a desired target clustering of G is reached. We use this technique to show both a negative and a positive complexity result. Firstly, we show that in general the problem is NP-complete. Secondly, we consider min-well-behaved graphs, which are graphs H having the property that for any k the graph H^{(k)} being the join of k copies of H has an optimal hierarchical clustering that splits each copy of H in the same optimal way. To optimally cluster such a graph H^{(k)} we thus only need to optimally cluster the smaller graph H. Co-bipartite graphs are min-well-behaved, but otherwise they seem to be scarce. We use the normalization procedure to show that also the cycle on 6 vertices is min-well-behaved.
Cite as

Svein Høgemo, Christophe Paul, and Jan Arne Telle. Hierarchical Clusterings of Unweighted Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hgemo_et_al:LIPIcs.MFCS.2020.47,
  author =	{H{\o}gemo, Svein and Paul, Christophe and Telle, Jan Arne},
  title =	{{Hierarchical Clusterings of Unweighted Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.47},
  URN =		{urn:nbn:de:0030-drops-127139},
  doi =		{10.4230/LIPIcs.MFCS.2020.47},
  annote =	{Keywords: Hierarchical Clustering}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.57
Typical Sequences Revisited - Computing Width Parameters of Graphs

Authors: Hans L. Bodlaender, Lars Jaffke, and Jan Arne Telle

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in ?(n²) time.
Cite as

Hans L. Bodlaender, Lars Jaffke, and Jan Arne Telle. Typical Sequences Revisited - Computing Width Parameters of Graphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.STACS.2020.57,
  author =	{Bodlaender, Hans L. and Jaffke, Lars and Telle, Jan Arne},
  title =	{{Typical Sequences Revisited - Computing Width Parameters of Graphs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{57:1--57:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.57},
  URN =		{urn:nbn:de:0030-drops-119189},
  doi =		{10.4230/LIPIcs.STACS.2020.57},
  annote =	{Keywords: typical sequences, treewidth, series parallel digraphs, cutwidth, modified cutwidth}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.IPEC.2019
LIPIcs, Volume 148, IPEC'19, Complete Volume

Authors: Bart M. P. Jansen and Jan Arne Telle

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
LIPIcs, Volume 148, IPEC'19, Complete Volume
Cite as

14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{jansen_et_al:LIPIcs.IPEC.2019,
  title =	{{LIPIcs, Volume 148, IPEC'19, Complete Volume}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019},
  URN =		{urn:nbn:de:0030-drops-116409},
  doi =		{10.4230/LIPIcs.IPEC.2019},
  annote =	{Keywords: Theory of computation, Parameterized complexity and exact algorithms}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.IPEC.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Bart M. P. Jansen and Jan Arne Telle

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2019.0,
  author =	{Jansen, Bart M. P. and Telle, Jan Arne},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.0},
  URN =		{urn:nbn:de:0030-drops-114618},
  doi =		{10.4230/LIPIcs.IPEC.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.6
Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width

Authors: Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
We generalize the family of (sigma, rho)-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-r dominating set and distance-r independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as k-trapezoid graphs, Dilworth k-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, k-polygon graphs, circular arc graphs, complements of d-degenerate graphs, and H-graphs if given an H-representation. To supplement these findings, we show that many classes of (distance) (sigma, rho)-problems are W[1]-hard parameterized by mim-width + solution size.
Cite as

Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2018.6,
  author =	{Jaffke, Lars and Kwon, O-joung and Str{\o}mme, Torstein J. F. and Telle, Jan Arne},
  title =	{{Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.6},
  URN =		{urn:nbn:de:0030-drops-102074},
  doi =		{10.4230/LIPIcs.IPEC.2018.6},
  annote =	{Keywords: Graph Width Parameters, Graph Classes, Distance Domination Problems, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.21
Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width

Authors: Lars Jaffke, O-joung Kwon, and Jan Arne Telle

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
We give the first polynomial-time algorithms on graphs of bounded maximum induced matching width (mim-width) for problems that are not locally checkable. In particular, we give n^O(w)-time algorithms on graphs of mim-width at most w, when given a decomposition, for the following problems: Longest Induced Path, Induced Disjoint Paths and H-Induced Topological Minor for fixed H. Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc, Per- mutation and Circular Permutation graphs, Convex graphs, k-Trapezoid, Circular k-Trapezoid, k-Polygon, Dilworth-k and Co-k-Degenerate graphs for fixed k.
Cite as

Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2017.21,
  author =	{Jaffke, Lars and Kwon, O-joung and Telle, Jan Arne},
  title =	{{Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.21},
  URN =		{urn:nbn:de:0030-drops-85643},
  doi =		{10.4230/LIPIcs.IPEC.2017.21},
  annote =	{Keywords: graph width parameters, dynamic programming, graph classes, induced paths, induced topological minors}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.42
A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width

Authors: Lars Jaffke, O-joung Kwon, and Jan Arne Telle

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
We give a first polynomial-time algorithm for (Weighted) Feedback Vertex Set on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an n^{O(w)}-time algorithm that solves Feedback Vertex Set. This provides a unified algorithm for many well-known classes, such as Interval graphs and Permutation graphs, and furthermore, it gives the first polynomial-time algorithms for other classes of bounded mim-width, such as Circular Permutation and Circular k-Trapezoid graphs for fixed k. In all these classes the decomposition is computable in polynomial time, as shown by Belmonte and Vatshelle [Theor. Comput. Sci. 2013]. We show that powers of graphs of tree-width w-1 or path-width w and powers of graphs of clique-width w have mim-width at most w. These results extensively provide new classes of bounded mim-width. We prove a slight strengthening of the first statement which implies that, surprisingly, Leaf Power graphs which are of importance in the field of phylogenetic studies have mim-width at most 1. Given a tree decomposition of width w-1, a path decomposition of width w, or a clique-width w-expression of a graph G, one can for any value of k find a mim-width decomposition of its k-power in polynomial time, and apply our algorithm to solve Feedback Vertex Set on the k-power in time n^{O(w)}. In contrast to Feedback Vertex Set, we show that Hamiltonian Cycle is NP-complete even on graphs of linear mim-width 1, which further hints at the expressive power of the mim-width parameter.
Cite as

Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.STACS.2018.42,
  author =	{Jaffke, Lars and Kwon, O-joung and Telle, Jan Arne},
  title =	{{A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.42},
  URN =		{urn:nbn:de:0030-drops-85348},
  doi =		{10.4230/LIPIcs.STACS.2018.42},
  annote =	{Keywords: graph width parameters, graph classes, feedback vertex set, leaf powers}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.14
On Satisfiability Problems with a Linear Structure

Authors: Serge Gaspers, Christos H. Papadimitriou, Sigve Hortemo Sæther, and Jan Arne Telle

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
It was recently shown [Sæther, Telle, and Vatshelle, JAIR 54, 2015] that satisfiability is polynomially solvable when the incidence graph is an interval bipartite graph (an interval graph turned into a bipartite graph by omitting all edges within each partite set). Here we relax this condition in several directions: First, we show an FPT algorithm parameterized by k for k-interval bigraphs, bipartite graphs which can be converted to interval bipartite graphs by adding to each node of one side at most k edges; the same result holds for the counting and the weighted maximization version of satisfiability. Second, given two linear orders, one for the variables and one for the clauses, we show how to find, in polynomial time, the smallest k such that there is a k-interval bigraph compatible with these two orders. On the negative side we prove that, barring complexity collapses, no such extensions are possible for CSPs more general than satisfiability. We also show NP-hardness of recognizing 1-interval bigraphs.
Cite as

Serge Gaspers, Christos H. Papadimitriou, Sigve Hortemo Sæther, and Jan Arne Telle. On Satisfiability Problems with a Linear Structure. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.IPEC.2016.14,
  author =	{Gaspers, Serge and Papadimitriou, Christos H. and S{\ae}ther, Sigve Hortemo and Telle, Jan Arne},
  title =	{{On Satisfiability Problems with a Linear Structure}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.14},
  URN =		{urn:nbn:de:0030-drops-69412},
  doi =		{10.4230/LIPIcs.IPEC.2016.14},
  annote =	{Keywords: Satisfiability, interval graphs, FPT algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.212
Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set

Authors: Jisu Jeong, Sigve Hortemo Sæther, and Jan Arne Telle

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A \cup B \cup C=X and |A|,|B|,|C| <= k such that any subset of X that is a minimal separator of H is a subset of either A, B or C. Treewidth and branchwidth have alternative definitions through intersections of subtrees, where treewidth focuses on nodes and branchwidth focuses on edges. We show that mm-width combines both aspects, focusing on nodes and on edges. Based on this we prove that given a graph G and a branch decomposition of mm-width k we can solve Dominating Set in time O^*(8^k), thereby beating O^*(3^{tw(G)}) whenever tw(G) > log_3(8) * k ~ 1.893 k. Note that mmw(G) <= tw(G)+1 <= 3 mmw(G) and these inequalities are tight. Given only the graph G and using the best known algorithms to find decompositions, maximum matching width will be better for solving Dominating Set whenever tw(G) > 1.549 * mmw(G).
Cite as

Jisu Jeong, Sigve Hortemo Sæther, and Jan Arne Telle. Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 212-223, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{jeong_et_al:LIPIcs.IPEC.2015.212,
  author =	{Jeong, Jisu and S{\ae}ther, Sigve Hortemo and Telle, Jan Arne},
  title =	{{Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{212--223},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.212},
  URN =		{urn:nbn:de:0030-drops-55846},
  doi =		{10.4230/LIPIcs.IPEC.2015.212},
  annote =	{Keywords: FPT algorithms, treewidth, dominating set}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact